#include <iostream>
#include <vector>
using namespace std;

// 77.组合
// 给出两个整数n和k，求在1...n这n个数字中选出k个数字的所有组合。
//- 如 n = 4，k = 2
//- 结果为[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
class Solution {
private:
    vector<vector<int>> res;
    // 求解C(n, k)，当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    void generateCombinations(int n, int k, int start, vector<int> &c) {
        if(c.size() == k) {
            res.push_back(c);
            return;
        }

        for(int i = start; i <= n; i++) {
            c.push_back(i); // 放入i
            generateCombinations(n, k, i + 1, c);   // i以前的数字已经尝试过放入c中了
            c.pop_back();   // 将之前放入的拿出来，尝试放入下一个i
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        res.clear();
        // 边界条件
        if(n <= 0 || k <= 0 || k > n) {
            return res;
        }

        vector<int> c;
        generateCombinations(n, k, 1, c);   // 从1开始搜索

        return res;
    }
};
int main() {
    vector<vector<int>> res = Solution().combine(4,2);
    for(int i = 0; i < res.size(); i++) {
        for(int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
    return 0;
}
